//
// Created by wangxn on 2016/4/19.
//
/**
 * RSA 算法不同于DES的各种置换和替换操作,
 * RSA的加密解密数据围绕着模幂运算,一种取模计算.
 *
 * 取模计算:
 *      整数运算中的一种常见形式,
 *      只是当对n取模时, 每一个结果x由集合{0,1,...,n-1}中的成员取代,
 *      这样x mod n 的结果就是x/n的余数.
 *      比如 40 mod 11 = 7, 因为40 / 11 = 3, 余数是7.
 *      模幂运算就是计算 (a的b次方 mod n)的过程
 *
 * 公钥加密,私钥解密
 *
 * 生成密钥时,需要遵循几个步骤以确保公钥和私钥的这种关系能够正常工作.
 * 这些步骤也确保没有实际方法能够从一个密钥推出另一个
 *
 * 素数(质数):
 *      在打印1的整数中, 仅有1及其本身能将它整除的数, 比如: 2,3,5,7,11,13,17...
 * 奇数:
 *      相对与偶数,不能被2整除的整数
 *
 * 1.首先选择两个大的素数,记为p和q,这两个数应该至少有200位.
 * 2.计算n :
 *          n = p * q;
 * 3. 选择一个小的奇数额e,
 *          3.1 它将作为公钥的一部分
 *          3.2 它与 (p - 1) * (q - 1)不能有相同的因子,就是说e与 (p -1)(q-1)是互为素数关系.
 *          3.3 通常选择 3, 17, 以及 65 ,537 作为e的值
 * 4. 计算相对应的值d, d将作为私钥的一部分. 如下公式:
 *          d = e(-1次方) mod (p-1)(q-1)
 *      理解这个公式:
 *            计算e的倒数对(p-1)(q-1)的取模结果
 *            也可以理解为 当d为多少时可以满足 e d mod (p-1)(q-1) = 1
 *            比如,在等式17d mod 180 = 1中, d的一种可能值是53.其他可能值是233, 413, 593
 *      在实践中可以利用欧几里德扩展算法来计算模乘法逆元.
 *      这里只能使用d和e,但是不能用来获取他们的值
 *
 * 5. 现在有了e和d的值, 将 (e, n)作为公钥P, 将 (d, n)作为私钥S并保持其不可见.可以表示为:
 *      P = (e, n)   ,  S = (d, n)
 *
 * 6. 加密方使用P来加密数据, 解密方使用S来解密.
 *
 * 7. 计算P和S的步骤起源于欧拉函数中的一个有趣性质.
 *          欧拉函数记为 f(n)
 *          定义所有小于n的正整数里和n互素的整数的个数.
 *          只有当两个整数的唯一公因子为1时,才说这两个整数是互素的.
 *          举一个欧拉函数的例子: f(8) = 4,因为一共只有4个比8小的整数是互素的,他们是1,3,5,7
 *
 *          欧拉方程有两个性质对RSA算法来说是特别重要的.
 *          1. 当n是素数是, f(n) = n-1; 因为n的唯一因子是1和n,因此n与其之前的所有n-1个正整数都是互素的
 *          2. 对于任意小于n且与n互素的正整数a,都有
 *                  a(f(n)次方) mod n = 1
 *                  比如:  1(4次方) mod 8 = 1,  3(4次方) mod 8 = 1, 5(4次方) mod 8 = 1,
 *             可以调整公式为
 *                  (a) * (a(f(n)次方) mod n ) = 1
 *             继续调整: a((f(n) + 1)次方) mod n = a
 *             举例:  1(5次方) mod 8 = 1, 3(5次方) mod 8 = 3, 5(5次方) mod 8 = 5, 7(5次方) mod 8 = 7
 *             反向推论: 对于某些等式 c = m(e次方) mod n,
 *             我们可以找出一个值d , 使得  c(d次方) mod n = m
 *             这就是RSA算法中允许加密数据,之后再解密回原文的恒等式, 按如下方式表示:
 *             c(d次方) mod n = (m(e次方))(d次方) mod n
 *                           = m((e*d)次方) mod n
 *                           = m( (f(n) + 1)次方 ) mod n
 *                           = m mod n
 *
 *
 * 8.分组大小
 *    要确保分组可以保存的最大数值要小于n的位数
 *          比如 选择的p和q都是200位数字的素数,那么n的结果将小于400位.
 *          分组所能保存的最大值应该要尽量接近于400,通常先择比n小的2的最大整数次幂.比如如果n为209,则分组大小为7位,2的7次幂为128比209小,2的8次幂又大于208
 *
 *
 * 9. 基本的实现比较简单,
 * 10.问题
 *      要是RSA的安全性得到保障,
 *      必须使用很大的整数,这就使得事情变得复杂.
 *      特别是所有的计算中使用到的整数位数必须是密钥位数的2倍.
 *      所以,如果密钥是个200位的整数,就需要一种抽象数据类型来支持至少400位的整数.
 *      有其他的可用函数库,用于大整数的处理
 *      这里的Huge类型是unsiged long, 只能提供10位的十进制的支持,这里的实现只能支持最多5位整数的密钥.
 *
 *
 */

#include "encrypt.h"
#include "stdio.h"
#include "stdlib.h"


/**
 * 计算 a(b次方) mod n 的值
 * a 代表明文分组
 * b 和 n 代表公钥的e和n成员
 *
 * 这里使用称为二进制平方-乘 的算法来计算模幂
 *
 * 二进制平方-乘算法 避免了当a和b都很大时计算a的b次方会出现超大中间值的问题
 * 用二进制平方-乘算法计算   a的b次方 mod n ,主要是多个开平方运算的结果
 *
 * 1.  将b表示为二进制形式,然后从最右边的位开始处理
 * 2.  对于b中的每个位,求出a的平方对n取模的结果,并将这个结果赋值给a
 * 3.  每当遇到b中为1的位时,将当前的a值乘上另一个寄存器y(初始值为1),并将结果再赋值给y
 * 4.  一旦迭代至b的最高有效位,y的值就是 a的b次方 mod n 的结果,在这个过程中,产生的最大值是a的平方
 */
static  Huge modexp(Huge a, Huge b, Huge n) {
    Huge y = 1;

    while (b != 0) {
        if (b & 1) { //最低位和1与, b中最低位为1是,处理if判断
            y = (y * a) % n;
        }
        a = (a * a) % n;
        b = b >> 1; //b左移一位
    }
    return y;
}

/**
 * 可以理解为
 *
 *      明文(e次方) mod n = 密文
 *
 */
void rsa_encipher(Huge plaintext,
                  Huge *ciphertext,
                  RsaPubKey pubKey) {

    *ciphertext = modexp(plaintext, pubKey.e, pubKey.n);
    return;
}

/**
 * 可以理解为
 *
 *      密文(d次方) mod n = 明文
 *
 */
void rsa_decipher(Huge ciphertext,
                  Huge *plaintext,
                  RsaPriKey prikey) {

    *plaintext = modexp(ciphertext, prikey.d, prikey.n);
    return;
}
